Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a network transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to recreate the image.
Many different data compression techniques exist in the prior art. Compression techniques can be divided into two broad categories, lossy coding and lossless coding. Lossy coding involves coding that results in the loss of information, such that there is no guarantee of perfect reconstruction of the original data. The goal of lossy compression is that changes to the original data are done in such a way that they are not objectionable or detectable. In lossless compression, all the information is retained and the data is compressed in a manner that allows for perfect reconstruction.
In image and video coders, images are typically partitioned into sets of blocks. Each block is transformed and quantized into a set of coefficients. The coefficients may be created by applying transforms (e.g., a Discrete Cosine Transform (DCT), a wavelet transform) to data. For example, in JPEG, a DCT transform is applied to image data to create coefficients. Subsequently, these coefficients may be quantized. For each block, information describing which coefficients have a non-zero value must be transmitted.
Quantized coefficients are typically arranged into a one-dimensional array of values. The ordering of coefficients within the array is determined by a scan order, for example a zig-zag scan order. The positions of non-zero coefficients are then coded using run-length coding methods.
Scanning methods often have limited efficiency. For example, with respect to the zig-zag scanning method, when a block contains either only horizontal or vertical frequencies, a large number of zero coefficients are visited along the zig-zag pattern resulting in inefficiencies.